#include "myTree.h"
#include <algorithm>

using namespace std;

TreeNode non = TreeNode();


TreeNode::TreeNode(char d, TreeNode* lc, TreeNode* rc, NodeTag l, NodeTag r){
    data = d;
    leftChild = lc;
    rightChild = rc;
    lTag = l;
    rTag = r;
}

TreeNode::~TreeNode()=default;

TreeNode::TreeNode(){
    data = '@';
    leftChild = NULL;
    rightChild = NULL;
    lTag = Link; 
    rTag = Link;
}

void TreeNode::printNode()
{
    cout << this->data;
}

MyTree::MyTree(){
    root = NULL;
    isThread = 0;
}

void MyTree::forward(TreeNode*& M, const char origin[], int &a){
    if(origin[a] == '@'){
        M = NULL;
        a ++;
    }
    else{
    M = new TreeNode;
    M -> data = origin[a];
    M -> lTag = Link;
    M -> rTag = Link;
    a ++;
    forward(M -> leftChild, origin, a);
    forward(M -> rightChild, origin, a);
    }
}


MyTree::MyTree(const char origin[]){
    isThread = 0;
    int a = 0;
    forward(root, origin, a);
}

void MyTree::copy(TreeNode*& p, TreeNode* p2){
    if(p2){
        p = new TreeNode;
        p -> data = p2 -> data;
    if ((p2 -> leftChild) && (p2 -> lTag == Link)){
        copy(p -> leftChild, p2 -> leftChild);
    }
    if ((p2 -> rightChild) && (p2 -> rTag == Link)){
        copy(p -> rightChild, p2 -> rightChild);
    }
    }
}

MyTree::MyTree(const MyTree& ftree){
    isThread = ftree.isThread;
    copy(root, ftree.root);
}

void MyTree::destroy(TreeNode*& p){
   if (p == NULL) {
        return;  // Return early if the pointer is null.
    }
    if (p->leftChild != NULL) {
        destroy(p->leftChild);  // Recursively destroy left child.
    }
    if (p->rightChild != NULL) {
        destroy(p->rightChild);  // Recursively destroy right child.
    }
    delete p;  // Delete the current node.
}

MyTree::~MyTree() = default;
//{
//     destroy(root);
//     root = NULL;
// }

void MyTree::printpre(TreeNode* p) {
    p->printNode();  // Print the current node's data.
    if ((p->leftChild) && (p -> lTag == Link)) {
        printpre(p->leftChild);  // Recursively print left child.
    }
    if ((p->rightChild)&& (p -> rTag == Link)) {
        printpre(p->rightChild);  // Recursively print right child.
    }
}

void MyTree::printin(TreeNode* p){
    if ((p -> leftChild) && (p -> lTag == Link)){
        printin(p -> leftChild);
    }
    p -> printNode();
    if ((p -> rightChild) && (p -> rTag == Link)){
        printin(p -> rightChild);
    }
}

void MyTree::printaft(TreeNode* p){
    if ((p -> leftChild) && (p -> lTag == Link)){
        printaft(p -> leftChild);
    }
    if ((p -> rightChild) && (p -> rTag == Link)){
        printaft(p -> rightChild);
    }
    p -> printNode();
}

void MyTree::preOrderTraverse(){
    printpre(root);
}

void MyTree::inOrderTraverse(){
    printin(root);
}

void MyTree::postOrderTraverse(){
    printaft(root);
}   //后序遍历

void MyTree::nodecount(TreeNode* p, int &a){
    if((p -> leftChild) && (p -> lTag == Link)){
        nodecount(p->leftChild, a);
    }
    if((p -> rightChild ) && (p -> rTag == Link)){
        nodecount(p->rightChild, a);
    }
    if(((p -> rightChild == NULL) && (p -> leftChild == NULL)) || ((p -> rTag == Thread) && (p -> lTag == Thread))){
        a ++;
    }
}

int MyTree::countLeaf(){
    int a = 0;
    nodecount(root, a);
    return a;
}

int MyTree::nodedepth(TreeNode* p){
    if(p == NULL){
        return 0;
    }
    if((p -> lTag == Thread) && (p -> rTag == Thread)){
        return 1;
    }
    else {
    int a = 0, b = 0;
    if(p -> lTag == Link)
    a = nodedepth ( p->leftChild );
    if(p -> rTag == Link)
    b = nodedepth ( p->rightChild); 
    return (a > b) ? a + 1 : b + 1; 
} 
}

int MyTree::countHeight(){
    return(nodedepth(root));
}          //计算树的深度

bool MyTree::isThreadedTree(){
    return isThread;
}

bool MyTree::inOrderThreading(){
    isThread = 1;
    TreeNode* pre = NULL;
    threading(root, pre);
    return 1;
    }

void MyTree::threading(TreeNode*& p, TreeNode*& pre){
    if(p){
    if(p -> leftChild != NULL)
    threading(p -> leftChild, pre);
    if(p -> leftChild == NULL){
        p -> lTag = Thread;
        p -> leftChild = pre;
    }
    if((pre != NULL) && (pre -> rightChild == NULL)){
        pre -> rTag = Thread;
        pre -> rightChild = p;
    }
    pre = p;
    if(p -> rightChild != NULL)
    threading(p -> rightChild, pre);
    }
}

void MyTree::pre(TreeNode* p, const char& v, TreeNode& oi){
    if(p){
    if(p -> data == v){
        oi = *p;
        return;
    }
    else{
        if ((p -> leftChild !=  NULL)&&(p -> lTag == Link))
            pre(p -> leftChild, v, oi);
        }
        if ((p -> rightChild != NULL)&&(p -> rTag == Link))
        {
            pre(p -> rightChild, v, oi);
        }
    }
}

TreeNode& MyTree::locateNode(const char& v){
    TreeNode a = TreeNode();
    TreeNode& oi = a;
    pre(root, v, oi);
    if(oi.data == '@')
    return non;
    return oi;
}  //结点定位

TreeNode& MyTree::preNode(const TreeNode& tree){
    if((tree.leftChild != NULL) && (tree.lTag == Link)){
        TreeNode* p = tree.leftChild;
    while((p -> rightChild != NULL) && (p -> rTag == Link)){
        p = p -> rightChild;
    }
    return *p;
    }
    return *tree.leftChild;
} //获取前驱结点
TreeNode& MyTree::nextNode(const TreeNode& tree){
    if((tree.rightChild != NULL) && (tree.rTag == Link)){
        TreeNode* p = tree.rightChild;
    while((p -> leftChild != NULL) && (p -> lTag == Link)){
        p = p -> leftChild;
    }
    return *p;
    }
    return *tree.rightChild;
}//获取后继结点

bool compare(const nnode& a, const nnode& b){
    return(a.weight > b.weight);
}

HuffmanTree::HuffmanTree(const int& n,const int d[]){
    nodenum = n;
    data = new nnode[n + n - 1];
    sumson = 0;
    for(int i = 0; i < nodenum; i ++){
        sumson += d[i];
        data[i].weight = d[i];
        data[i].parent = -1;
        data[i].leftChild = -1;
        data[i].rightChild = -1;
    } 
    sort(data, data + nodenum, compare);
    for(int y = 0; y < n - 1; y ++){
        int num1 = sumson, num2 = sumson;
        int pos1, pos2;
        for(int k = 0; k < y + nodenum; k ++){
            if((data[k].parent == -1)){
                if(data[k].weight < num1){
                    pos2 = pos1;
                    num2 = num1;
                    pos1 = k;
                    num1 = data[k].weight;
                }
                else if(data[k].weight < num2){
                    pos2 = k;
                    num2 = data[k].weight;
                }
            }
        }
        data[n + y].parent = -1;
        data[n + y].weight = num1 + num2;
        data[pos1].parent = n + y;
        data[pos2].parent = n + y;
        data[n + y].rightChild = pos2;
        data[n + y].leftChild = pos1;
    }
}

HuffmanTree::~HuffmanTree() = default;

void HuffmanTree::printHuffmanCodes(){
    for(int i = 0; i < nodenum; i ++){
        cout << data[i].weight;
        cout << ":";
        int p = i;
        int write = 0;
        int* pri = new int [nodenum - 1];
        while(data[p].parent != -1){
            int u = data[p].parent;
            if(p == data[u].rightChild){
                pri[write] = 1;
            }
            else
                pri[write] = 0;
            p = u;
            write ++;
        }
        for(int i = 0; i < write; i ++){
            cout << pri[write - 1 - i];
        }
        cout << endl;
        delete [] pri;
    }
}